1. Field of the Invention
The present invention relates to digital data transmission systems and, more particularly, to coding structures and techniques for use in digital data transmission systems.
2. Description of the Related Art
When a transmitter sends a signal pattern that, by pre-arrangement, a receiver expects, this has the potential both to transmit timing information and provide for range measurement, namely determining the distance between the transmitter and the receiver. But the receiver's measurement of the time of arrival of the expected pattern depends both on the range and on the difference between the transmitter's and the receiver's timing, or internal clocks. Thus, the measurement is called a pseudorange. If the range were known, the time difference could be determined; or if the time error were negligible, the range could be determined. But usually there are both range and time uncertainties. In some applications, such as in the Global Positioning System (GPS) described in more detail below, multiple transmitters permit multiple pseudorange measurements; and, according to linear mathematics, when there are more knowns (e.g., measurements) than unknowns (e.g., uncertainties), the unknowns can be calculated.
In other applications, the expected pattern is simply a preamble to a message, and detecting the preamble pattern indicates the precise timing of the start of the message. In these applications, the timing and range uncertainties are not a problem because they apply equally to the preamble and to the message. Start-of-message timing, or detecting the start of a message, is especially important when the message is encrypted, because the message will not be recovered correctly if the decryption process is started at the wrong time.
In any case, a single pulse or simple signal feature does not convey timing reliably, because noise can easily obscure such a signal. Repeating a simple pattern (such as 010101 . . . ) is more reliable, but is ambiguous because the first “01” is indistinguishable from the second and third “01”, for example. Thus, the pattern generally needs to be complex.
A pseudorandom code (also called a pseudonoise, or PN code), such as a maximum-length binary code (m-sequence), is often used to transmit timing information, because such codes are ideal for reliably detecting the time of arrival of a signal in the presence of noise. The code can be sent repeatedly, in which case the timing is analogous to the ticking of a clock with each repetition of the code corresponding to a clock tick. This code can be combined with other data that effectively identifies each ‘tick’ as distinct from the others, thus providing more complete time information such as the precise time of day. When noise is present, making the detection of the signal unreliable, repeating the code provides multiple opportunities to detect the timing.
An example of a system that uses PN codes is the Global Positioning System (GPS). The GPS system is a satellite based navigation system in which a receiver receives signals from a constellation of satellites and determines its position in three dimensions and determines the time. A GPS receiver determines its position and the time based on ranging measurements to several satellites. The ranging measurements are made based on the propagation delay of signals transmitted by the satellite and received by the receiver. The precision of those ranging measurements depends on the receiver's ability to synchronize its clock with the satellites' clocks. Accordingly, transferring timing information is an important feature in the GPS system.
In order to accurately make the ranging measurement and transfer timing information the GPS satellites transmit two signals using at least two PN codes, the so-called coarse acquisition (C/A) and precision (P) codes. The C/A code is 1023 bits long and repeats every millisecond with a chip rate of 1.023 MHz. The P code is much longer and repeats once per week, and is broadcast at a chip rate of 10.23 MHz, and therefore provides higher precision. Using the longer P code to make pseudorange measurements avoids ambiguities in time differences between the satellite's clock and the receiver's clock. Also, as discussed in more detail below, the longer code provides better noise tolerance than a short code.
Because the C/A code is short and repeats often, it is relatively easy to detect and acquire. However, because the P code is so long it is very difficult if not impossible to acquire it without at least some measure of timing information about the phase of the P code. Superimposed on the C/A code is a navigational message that provides a longer cycle of timing and related information. Once a receiver acquires the C/A code it can extract timing information from the C/A code for use in acquiring the longer P code. Accordingly, two separate signals, carrying different length codes are used in time transfer applications such as in the GPS system.
The use of a short code to help acquire a longer code can be illustrated with the GPS system. In acquiring a coded signal a receiver must search for a specific portion of the code to detect its phase. To start its search a receiver must “guess” at certain search parameters. For example, in the case of the C/A code, there are 1023 possible starting positions for the code; and only one guess out of 1023 is correct. Usually, this is doubled. A receiver is designed to guess at half-chip intervals—because it does not know when any chip starts. But even when a receiver determines the correct guess, it still cannot distinguish one millisecond instance of the code from another, and this is known as ambiguity. In the case of the P code, if the receiver knows the time to within one second (plus or minus a half-second), then there are 10,230,000 possible starting positions for the code; and only one guess out of 10,230,000 is correct. It will take about 10,000 times longer to search the longer P code by testing the possibilities, however, there will be no ambiguity when the search is completed. But if the receiver first acquires the C/A code timing, it can determine when millisecond periods of the code start, even though they look alike because the same pattern repeats every millisecond. Knowing the C/A code's phase reduces the possibilities for the P-code phases to 10,000. That is, acquiring the C/A code signal helps the P code signal acquisition go 1023 times faster.
The code can also be sent once, generally to precisely mark the beginning of a message. An analogy for this situation is a starter's pistol marking the start of a race. When the code is sent only once, there is only one opportunity to detect the timing (for each message). For example, this is essentially the method used by the GPS cross-links (between satellites). The SINCGARS radio, a battlefield radio commonly used by the U.S. military, repeats a short code for a limited time and inverts the last repetition once before each message transmission. This last repetition corresponds to the code being sent once to mark the beginning of the message that follows the code. However, a burst of noise coinciding with this one-time code transmission will cause the system to fail and the message will be lost.
FIG. 1 shows a transmitter 1 and a receiver 9 used in a spread-spectrum system such as the GPS system. The transmitter includes a PN code generator 2 that is driven by a timing counter 3 and both are run based on a clock oscillator 4. The PN code generated by generator 2 is modulated with a carrier signal via modulator 5 which is driven by carrier oscillator 6. Optionally, data can be superimposed onto the code and carrier by using a modulo 2 adder 7. The transmitter 1 transmits the modulated carrier via antenna 8 to a receiver 9.
Receiver 9 receives the transmitted signal via an antenna 10 that provides the received signal to a demodulator 11. The demodulator 11 is driven by a carrier oscillator 12, and produces two signals out-of-phase by 90°. Those signals are designated as in-phase (I) and quadrature(Q) signals. These two out-of-phase signals are provided to a group of parallel correlators 13. The parallel correlators can include as many, and even more, correlators as the number of phases of the code to be tested. For example, if the code length is 1023 symbols, or chips, the parallel correlators 13 can consist of 1023 correlators, one correlator for each possible phase of the code. Multiple banks of the parallel correlators 13 can be used to correlate different signals, such as in this case where one bank correlates the I-signals and another bank correlates the Q-signals. The parallel correlators 13 are also provided with PN reference codes that correspond to the PN codes generated in the transmitter. PN code generator 14 generates the reference codes. The reference codes can be delayed to correspond to the various phases to be tested. Alternatively, the input signals, here the I and Q signals, can be delayed with various delays and correlated with a single PN code to test the different phases. The PN code generator 14 is driven by a local clock oscillator 15 and timing counters 16 which can effect the different timings for the PN reference codes. The local clock oscillator also drives timing counters 16.
The communications system shown in FIG. 1 shows the acquisition mode portion of the receiver. In the acquisition mode the receiver must resolve many concurrent uncertainties; but once these uncertainties are resolved, the receiver can enter the tracking mode which performs only comparatively minor adjustments to keep the receiver's timing locked onto the timing of the received signal. Table 1 below summarizes the uncertainties involved in acquiring a spread spectrum signal and the conventional strategies employed to resolve the uncertainties.
TABLE 1UncertaintyStrategyUnsure of carrier phaseProcess both I and Q phasesUnsure of carrier frequenciesTry several nearby frequencies (rangedepends on Doppler/frequencyuncertainty)Unsure of carrier phaseProcess both I and Q phasesUnsure of clock (symbol/chip)Sample at twice the symbol/ship ratetiming(e.g., 2 timing guesses per chip)Unsure of code phaseTry correlating at all possible codephases (range depends on timeuncertainty or code period)
When attempting to acquire a spread-spectrum signal the receiver initially does not know the correct carrier phase, so the conventional strategy is to process the signal with the two carrier phases signals, the I and Q signals, because at least one of these phases will be close enough to detect the signal, if the carrier frequency is set accurately enough that the phase does not rotate more than about 90 degrees during any given correlation. Each sample has an I and a Q component, also called I and Q data.
If the frequency uncertainty is too great, typically when the transmitter and/or receiver are moving, then the receiver will try to use a sufficient number of frequencies to cover the range of uncertainty. These different frequencies are often called Doppler bins, when the Doppler effect is the largest contributor to the frequency uncertainty.
The receiver also initially does not know the correct clock (chip) phase, although typically it can set the clock frequency close enough to enable detection. The conventional strategy is to sample the received signal at twice the chip rate. Among the odd samples and even samples, at least one of these sample sequences will be close enough to the ideal timing to detect the signal.
Finally, the receiver initially does not know the timing of the PN code. For a repeated n-chip code, there are n code timing possibilities. If the repeat cycle (i.e., the code length) is shorter than the time uncertainty of the receiver, the code will not, by itself, resolve all of the receiver's time uncertainty. If the code length is greater than the range of the receiver's time uncertainty, then the number of code timing possibilities is equal to the number of chips in the range of the receiver's time uncertainty.
The receiver can find the correct carrier frequency and phase and correct chip and code timing faster to the degree that it has more correlators. The correlations of I and Q data are usually combined and counted as one correlation. When a short code such as the C/A code is repeated, it is common practice to provide enough correlators operating concurrently (i.e., “in parallel”) to try all code phases, both odd and even chip samples, and to process both I and Q data. Some parallel correlator designs are based on delaying the reference code to obtain different alignments with the received data. Other designs are based on delaying the received signal samples to obtain different alignments with the reference code. In either case, each correlation spans one code length, and each correlation starts and ends at a different time. Thus, one correlation is produced per sample period. A set of correlations may need to be repeated for each Doppler bin, or frequency guess.
However, when the code length is long, such as with the GPS P code, the number of correlations needed to detect the code phase becomes unreasonably large, and other methods must be used to detect the phase of the long code. For example, in the GPS system a separate signal is broadcast using the shorter C/A code to assist in detecting the longer P code.
Whether the code is repeated or transmitted only once, there are many suitable codes and code generators that are known and can be used. Generally, the code is detected in a receiver by one or more correlators that compare the noisy received signal with a noise-free reference code generated at the receiver. A conventional PN code generator 9 is shown in detail in FIG. 2. The PN code generator of FIG. 2 includes a shift register 20 and a modulo-2 adder 21. In this example, the shift register is six bits long, although it can be longer or shorter as needed. The six flip-flops of shift register 20 are synchronously driven by a clock signal. Modulo-2 adder 21 adds the first and sixth bits of the shift register, and inserts the result into the first position of register 20. In this manner, a maximal-length PN sequence is produced.
The receiver can use the same code generator as the transmitter thereby ensuring that the codes are identical. Each correlator effectively computes the sum of the products of received bits times reference bits. The output of a correlator is greatest when its received signal input and reference code input are time-aligned, or in-phase with one another, and small when not aligned, or out-of-phase with one another. Increased noise makes this correlation product increasingly unreliable.
At the outset, the correct time alignment between the received code and the reference code is unknown, so the receiver must try all possible alignments. For fast detection, a receiver typically will provide one correlator for each possible alignment, to try all alignments simultaneously. The alignments are spaced closely enough that at least one correlator will be sufficiently aligned to detect the code. The set of alignments is achieved either by delaying the reference code by successive small amounts, such as one bit at a time, or by delaying the received signal. Alternatively, a receiver can try the phase alignments sequentially, reducing the number of correlators, and thereby reducing the hardware cost but increasing the search time and thereby increasing the time cost. The simultaneous and sequential correlation methods can be combined, but the hardware cost times the time cost is proportional to the number of possible time alignments.
The outputs of the correlators are compared, and the correlator with the highest output indicates the correct alignment. Since the timing of the reference generator is known, and the delay used with the correlator that provides the strongest output is known, the timing of the signal, although obscured by noise, is then known.
It is established in theory and in practice that if the length of the code is multiplied by n, equal performance, namely reliable detection, can be obtained with n times as much noise power, for the same signal power and other factors. The longer code period also provides more timing information. But this increases, by n-fold, the number of alignments that must be tried, thus also the number of correlations and the size of the correlator sums. This increases some costs n-fold, and other costs even more.
Alternatively, shorter codes can be used and the correlation can be summed over n repetitions of the code. This also increases the size of the correlator sums, and related costs, and the longer correlation can handle n times as much noise power. But summing over repetitions of the shorter code does not provide more timing information, because the number of identifiable code alignments is not changed.
For example, suppose a communications system uses a code one second long that repeats. The receiver finds a maximum correlation, or detects a code alignment, once per second (like a one-second clock tick). A double-length (two second) correlation can handle twice as much noise, but there is still one alignment per second. A two-second correlation on a two-second code will also handle twice the noise, but will have one alignment every two seconds. The receiver acquires more timing information with the two-second code, because it can distinguish odd and even seconds. But the longer code has twice as many possible phase positions, which doubles the cost.
Accordingly, conventional data transmission systems that use long PN codes have used expensive hardware solutions or employ two separate signals with different codes, with the associated hardware costs and complexities, such as in the GPS system discussed above, to acquire and use the more noise tolerant long codes in a timely manner.